Másele #1075

Yad 16 MB Waqıt 1000 ms Qıyınshılıǵı 47 %

#Perebor

#Dinamik dasturlash

#Depth-First Search

Bayram stoli

Bitvoy do'stlari bilan bayram uyushtirmoqchi. Ammo u do'stlari uchun to'g'ri to'rtburchak shaklidagi stol buyurtma qilmoqchi. U juda sahiy. Shuning uchun iloji boricha ko'proq mehmon o'tirishi mumkin bo'lgan stol buyurtma qilmoqchi. Bunda stol sig'imi uning perimetri bilan bir xil. Bitvoy eng ko'pi bilan necha nafar do'stini taklif qilishi mumkinligi aniqlang. Stolda o'zi ham o'tirishi kerak.

Kiriwshi maǵlıwmatlar:

Kirish faylida birinchi qatorda Bitvoyning uyini o'lchamlari kiritiladi. N, M\((1\le N, M \le 400)\).

Keyingi N qatorda Bitvoy uyining xaritasi M tadan belgi, bunda X -> bu joy allaqachon band, nuqta(.) -> bo'sh joyni anglatadi.

Shıǵıwshı maǵlıwmatlar:

Chiqish faylida Bitvoy nechta do'stini chaqirishi mumkin ekanligini chop eting.

Mısallar

#	input.txt	output.txt
1	1 1 .	3
2	10 10 ....X..... X......... .......... .......... .......... .......... .......X.. .......... ..X....... ...X......	27

Túsindirme:

1-testda:

Demak eng ko'pi bilan 2x2 o'lchamli stol buyurtma qilishi mumkin.

P = 2 * (1 + 1) = 4

O'zi ham borligi uchun 4 - 1=3.

2-testda:

Demak eng ko'pi bilan 10x4 o'lchamli stol buyurtma qilishi mumkin.

P = 2 * (4 + 10) = 28

O'zi ham borligi uchun 28 - 1=27.

Telegram Facebook

Sheshimin jiberiw

Bul ámeldi orınlaw ushın sistemaǵa kiriń, eger profilińiz bolmasa qálegen waqıtta dizimnen ótiwińiz múmkin